class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        opDict = {' ':-1, '+':0, '-':0, '*':1, '/':1}

        mid = []
        acc = ''
        for c in s:
            if c in opDict:
                if len(acc)!=0:
                    mid.append(int(acc))
                    acc = ''
                if c!=' ': mid.append(c)
            else:
                acc += c
        if len(acc)!=0:
            mid.append(int(acc))
            acc = ''
        
        op = []
        back = []
        for e in mid:
            if isinstance(e, int):
                back.append(e)
            else:
                while len(op)!=0 and opDict[op[-1]]>=opDict[e]:
                    back.append(op[-1])
                    op.pop()
                op.append(e)
        while len(op)!=0: back.append(op.pop())        

        num = []
        for e in back:
            if isinstance(e, int):
                num.append(e)
            else:
                f1 = num.pop()
                f0 = num.pop()
                if e=='+':
                    num.append(f0+f1)
                elif e=='-':
                    num.append(f0-f1)
                elif e=='*':
                    num.append(f0*f1)
                elif e=='/':
                    num.append(f0//f1)
        return num[0]
print(Solution().calculate('1+2*3+4'))